// Quadtree lying x-z plane.
#pragma once

#include "Vector2.h"
#include <vector>

#define MAX_STACK_SIZE	(max_depth+5) * 4
#define FMAGNET_INDUCING_DEPTH 10

typedef struct { 

	int* particle_index;
	int particle_num;

} Particle_quadtree;


class QuadTree {
	
public:
	typedef struct _NearFMagnetCallBack {

		QuadTree* qt;

		Vector2 pos;
		float dist2;
		int particle_num;

		int cnt;

		Vector2 mm;
		
		_NearFMagnetCallBack() { 
			dist2 = 100000.0f;
			particle_num = 0;
			cnt = 0;
		};

		__forceinline int size() { return cnt; };

	} NearFMagnetCallBack;


private:
	friend void AddFMagnetInQuad(QuadTree *qt);

	enum {
		X_AXIS = 0,
		Y_AXIS = 1,
		Z_AXIS = 2
	};

private:

	// static variable
	static void* particle_system;

	static struct _particle {
		Vector2* pos;
		Vector2* vel;
		Vector2* mm;
	} particle;

	static int max_particle;

	static int max_depth;
	static int num_nodes;
	static int minimum_depth;

	static QuadTree** stack;

private:

	Particle_quadtree m_particles;

	bool m_hasChild;
	bool m_hasInducingFMagnet;

	Vector2 m_centerPos;
	
	Vector2 m_startPos;
	Vector2 m_endPos;
	
	QuadTree* m_parent;				//parent node
	QuadTree* m_child[4];			//child node
	
	int m_depth;					

	Vector2 mm;

	NearFMagnetCallBack m_nearFmagnet;

public:

	QuadTree() {
		m_particles.particle_num = 0;
		m_particles.particle_index = NULL;

		m_parent = NULL;

		m_depth = 0;

		m_hasChild = false;
		m_hasInducingFMagnet = false;

	};

	~QuadTree() {

	}

	inline void SetBoundingBox(Vector2& startPos, Vector2& endPos) {
		m_startPos = startPos;
		m_endPos = endPos;

		m_centerPos = (m_startPos + m_endPos) * 0.5f;

	};

	static void SetParticleArray(Vector2* pos, Vector2* vel, Vector2* mm) {
		particle.pos = pos;
		particle.vel = vel;
		particle.mm = mm;

		stack = new QuadTree*[MAX_STACK_SIZE];
	};

	static void SetParticleSystem(void* ps) { particle_system = ps; };

	static void DeleteStack() { delete [] stack; };

	void CreateIndexList(int num) {
		m_particles.particle_index = new int[num];
		for (int i=0; i<num; i++) {
			m_particles.particle_index[i] = i;
		}
		m_particles.particle_num = num;
	}

	void DeleteIndexList() {
		if (m_particles.particle_index)
		delete[] m_particles.particle_index;
	}

	void DeleteAll() {
		if (m_hasChild) {
			for (int i=0; i<4; i++) {
				m_child[i]->DeleteAll();
				delete m_child[i];
				m_hasChild = false;
			}
		}
	}

	void SubDivide();

	void UpdateQuadTrees();

	void IncreaseDepth() {
		m_depth++;
		if (m_parent)
			m_parent->IncreaseDepth();			
	}

	int SortIndex(int* indexlist, int num, int axis);

	__forceinline Vector2 GetPtcPos(int idx) {
		return particle.pos[m_particles.particle_index[idx]];
	}

	__forceinline static int GetMaxDepth() { return max_depth; };

	// find the node that vector located
	QuadTree* FindNode(Vector2& pos);

	// return if aabb and quad are intersecting
	__forceinline bool isIntersectAABB(Vector2& min_aabb, Vector2& max_aabb);


	bool FindNearestPointWithInducedMagnet(Vector2& pos, float max_dist, NearFMagnetCallBack& out);
	bool FindNearestPointWithInducedMagnet(Vector2& pos, Vector2& min_aabb, Vector2& max_aabb, NearFMagnetCallBack& out);
	void FindNearestPointWithInducedMagnet();

	void FindDepthCallBack(int depth, void(*callback)(QuadTree*));
	void FindDepthFMagnet(int depth);

	__forceinline NearFMagnetCallBack getNearFMagnet() { return m_nearFmagnet; };

	__forceinline bool hasChildFMagnet(void) {
		//BT_PROFILE("hasChildFMagnet");
		if (m_hasChild) {
			for (int i=0; i<4; i++) {
				if (m_child[i]->HasInducingMagnet())
					return true;
			}
		}
		return false;
	}

	static void SetInducedFMagnet(QuadTree *qt) {
		while (1) {
			qt->m_hasInducingFMagnet = true;
			if (qt->m_parent && !qt->m_parent->m_hasInducingFMagnet)
				qt = qt->m_parent;
			else
				break;
		}
	}

	__forceinline bool HasInducingMagnet() {
		return m_hasInducingFMagnet;
	}

	__forceinline static Vector2 GetPosition(QuadTree* qt) {
		return qt->m_centerPos;
	}
	/*
	static void DrawPointAtCenter(QuadTree* qt) {
		if (!qt->m_particles.particle_num) return;
		glColor3f(0.1, 0.8, 0.0);
		glBegin(GL_POINTS);
		glVertex3f(qt->m_centerPos.x(), 0.1f, qt->m_centerPos.z());
		glEnd();
	}
	*/
	void DrawLine();

	Particle_quadtree getm_particles(){
		return m_particles;
	}
	int getmax_particle(){
		return max_particle;
	}
};


